Wireless networks have experienced increased development in the past decade. One of the most rapidly developing areas is mobile ad-hoc networks. Physically, a mobile ad-hoc network includes a number of geographically-distributed, potentially mobile nodes sharing a common radio channel. Compared with other type of networks, such as cellular networks or satellite networks, the most distinctive feature of mobile ad-hoc networks is the lack of any fixed infrastructure. The network is formed of mobile nodes only, and a network is created on the fly as the nodes transmit with each other. The network does not depend on a particular node and dynamically adjusts as some nodes join or others leave the network.
In a hostile environment where a fixed communication infrastructure is unreliable or unavailable, such as in a battle field or in a natural disaster area struck by earthquake or hurricane, an ad-hoc network can be quickly deployed and provide limited but much needed communications. While the military is still a major driving force behind the development of these networks, ad-hoc networks are quickly finding new applications in civilian or commercial areas. Ad-hoc networks will allow people to exchange data in the field or in a class room without using any network structure except the one they create by simply turning on their computers or PDAs.
As wireless communication increasingly permeates everyday life, new applications for mobile ad-hoc networks will continue to emerge and become an important part of the communication structure. Mobile ad-hoc networks pose serious challenges to the designers. Due to the lack of a fixed infrastructure, nodes must self-organize and reconfigure as they move, join or leave the network. All nodes are essentially the same and there is no natural hierarchy or central controller in the network. All functions have to be distributed among the nodes. Nodes are often powered by batteries and have limited communication and computation capabilities. The bandwidth of the system is usually limited. The distance between two nodes often exceeds the radio transmission range, and a transmission has to be relayed by other nodes before reaching its destination. Consequently, a network has a multihop topology, and this topology changes as the nodes move around.
The Mobile Ad-Hoc Networks (MANET) working group of the Internet Engineering Task Force (IETF) has been actively evaluating and standardizing routing, including multicasting, protocols. Because the network topology changes arbitrarily as the nodes move, information is subject to becoming obsolete, and different nodes often have different views of the network, both in time (information may be outdated at some nodes but current at others) and in space (a node may only know the network topology in its neighborhood and not far away from itself).
A routing protocol needs to adapt to frequent topology changes and with less accurate information. Because of these unique requirements, routing in these networks are very different from others. Gathering fresh information about the entire network is often costly and impractical. Many routing protocols are reactive (on-demand) protocols: they collect routing information only when necessary and to destinations they need routes to, and do not maintain unused routes. This way the routing overhead is greatly reduced compared to pro-active protocols which maintain optimal routes to all destinations at all time. This is important for a protocol to be adaptive. Ad Hoc on Demand Distance Vector (AODV), Dynamic Source Routing (DSR) and Temporally Ordered Routing Algorithm (TORA) are representatives of on-demand routing protocols presented at the MANET working group.
Examples of other various routing protocols include Destination Sequenced Distance-Vector (DSDV) routing which is disclosed in U.S. Pat. No. 5,412,654 to Perkins, and Zone Routing Protocol (ZRP) which is disclosed in U.S. Pat. No. 6,304,556 to Haas. ZRP is a hybrid protocol using both proactive and reactive approaches.
These conventional routing protocols use a best effort approach in selecting a route from the source node to the destination node. Typically, the number of hops is the main criteria in such a best effort approach. In other words, the route with the least amount of hops is selected as the transmission route.
Quality-of-service (QoS) routing in mobile ad-hoc networks is gaining interest. To provide quality-of-service, the protocol needs not only to find a route but also to secure the resources along the route. Because of the limited, shared bandwidth of the network, and lack of central controller which can account for and control these limited resources, nodes must negotiate with each other to manage the resources required for QoS routes. This is further complicated by frequent topology changes. Due to these constraints, QoS routing is more demanding than best-effort routing.
Some examples of QoS routing approaches are set forth by Chenxi Zhu in the publication entitled “Medium Access Control and Quality-of-Service Routing for Mobile Ad Hoc Networks,” 2001, and by M. Mirhakkak et al. in the publication entitled “Dynamic Quality-of-Service for Mobile Ad Hoc Networks,” MITRE Corp., 2000. Zhu discusses establishing bandwidth guaranteed QoS routes in small networks whose topologies change at a low to medium rate. Mirhakkak et al. are concerned with resource reservation requests which specify a range of QoS values while the network makes a commitment to provide service within this range.
At each node, admission control is performed to forward traffic from other nodes. Typically, conventional admission control protocols provide for full disclosure regarding routes and connectivity. In other words, each node shares all route and connectivity data with other nodes so that the best-effort routes are selected overall.
A challenge to the advancement of ad-hoc network development is that of extending such networks to encompass large numbers of nodes. One prior art attempt to do so utilizes “spine” routing, such as in the optimal spine routing (OSR) approach disclosed by Das et al. in “Routing in Ad-Hoc Networks using Minimum Connected Dominating Sets,” IEEE Int. Conf. On Commun. (ICC '97), 1997. In this approach, a spine or “virtual backbone” is defined such that each network node is no more than one hop from a spine node. Global topology (link state) is maintained at each spine node, and a link-state routing algorithm is run at each spine node to produce current routes to every destination.
Another related approach is clustered spine routing (CSR), which is disclosed by Das et al. in “Routing in Ad-Hoc Networks using a Spine,” IEEE Int. Conf. On Computer Commun. and Networks (IC3N '97), 1997. this approach is intended to extend the applicability of spine routing to larger network sizes by grouping the nodes in clusters and adding a second hierarchical level to the OSR approach. Yet another approach is known as partial knowledge spine routing (PSR) which is disclosed by Sivakumar et al. in “The Clade Vertebrata: Spines and Routing in Ad-Hoc Networks,” IEEE Symposium On Computer and Commun., 1998.
One common characteristic of each of the above prior art cluster/spine approaches is that they each rely on proactive routing. One potential drawback of proactive routing is that it typically requires a significant amount of routing overhead to maintain optimal routes to all destinations at all times. This problem may become particularly acute when applied to ad-hoc networks including a very large number of nodes. Other difficulties which may be faced when implementing cluster/spine approaches are how to efficiently associate nodes with clusters and designate cluster leader nodes for each cluster.